package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         124,
		Discription: "二叉树最大路径和（可能有负数！）",
		Level:       3,
		Labels: map[string]int{
			"动态规划": 1,
			"二叉树":  1,
			"递归":   1,
			"回溯":   1,
		},
	})
}

// MaxPathSum 路径有两种：只经过一边子树的；两边子树都经过的
//
//	@param root
//	@return int
func MaxPathSum(root *ds.TreeNode) int {
	maxSum := root.Val
	var maxContribute func(*ds.TreeNode) int
	maxContribute = func(node *ds.TreeNode) int {
		if node == nil {
			return 0
		}

		//可能有负数，所以要跟0比
		//比0小就舍弃这一分支，相当于路径不经过这
		leftContribute := max(maxContribute(node.Left), 0)
		rightContribute := max(maxContribute(node.Right), 0)
		//经过当前节点但不经过父节点的路径最大值
		passBySum := leftContribute + rightContribute + node.Val
		if passBySum > maxSum {
			maxSum = passBySum
		}
		//return的是当前节点往上传的最大贡献，只能选经过左子树或者右子树
		return max(leftContribute, rightContribute) + node.Val
	}

	maxContribute(root)
	return maxSum
}
